An enterprise customer may build a Virtual Private Network (VPN) by connecting multiple sites or users over a network operated by a telephony or network service provider. For example, the enterprise customer's devices such as Customer Edge Routers (CERs) may be connected to the network service provider's Layer 2 network through a Provider Edge Router (PER). The Layer 2 network can be an Asynchronous Transfer Mode (ATM) network and/or a Frame Relay (FR) network. The voice and data packets from the customer premise may traverse the Layer 2 network prior to reaching an IP network. For example, a virtual connection such as a Permanent Virtual Circuit (PVC) may be established for the customer through a Layer 2 network, e.g., an ATM network. However, the network may have to re-route a virtual connection due to network events such as failures, maintenance activities, etc. Due to infrastructure build-out and cost limitations, the re-routes may result in less than optimal routing. The customer traffic may experience increased latency, packet loss, trunk over utilization, etc.